A transduction, in the sense of this paper, is a n-ary word relation (which may be a function) describable by a finite directed labeled graph. The notion of n-ary transduction is co-extensive with the Kleenean closure of finite n-ary relations. The 1-ary transductions are exactly the sets recognizable by finite automata. However, for n > 1 the relations recognizable by finite automata constitute a proper subclass of the n-ary transductions. The 2-ary length-preserving transductions constitute the equilibrium (potential) behavior of 1 -dimensional, bilateral iterative networks. The immediate consequence relation of various primitive deductive (respectively computational) systems, such as Post normal systems (respectively Turing machines) are examples of transductions. Other, richer, deductive systems have immediate consequence relations which are not transductions. The closure properties of the class of transductions are studied. The decomposition of transductions into simpler ones is also studied.
By: C. C. Elgot, J. E. Mezei
Published in: RC1017 in 1963
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .